package ljl.alg.jianzhioffer.round3.easy;

import java.util.*;

public class _50_firstUniqChar {
    /**
     * 这个名为 benbi 的解法居然是最快的
     * */
    class benbi1 {
        public char firstUniqChar(String s) {
            LinkedHashSet<Character> candidate = new LinkedHashSet<>();
            HashSet<Character> visited = new HashSet<>();
            for (char c : s.toCharArray()) {
                if (!visited.contains(c)) {
                    visited.add(c);
                    candidate.add(c);
                }
                else
                    candidate.remove(c);
            }
            return candidate.isEmpty() ? ' ' : candidate.iterator().next();
        }
    }

    class benbi2 {
        public char firstUniqChar(String s) {
            LinkedHashMap<Character, Integer> map = new LinkedHashMap<>();
            for (char c : s.toCharArray()) {
                map.put(c, map.getOrDefault(c, 0) + 1);
            }
            for (Character c : map.keySet()) {
                if (map.get(c) == 1)
                    return c;
            }
            return ' ';
        }
    }

    class lufei1 {

        /**
         * 这是把每个字符标记一下，出现过多余一次的会变成 false
         * 然后遍历字符串挨个判断返回第一个 true
         * */
        public char firstUniqChar(String s) {
            HashMap<Character, Boolean> dic = new HashMap<>();
            char[] sc = s.toCharArray();
            for(char c : sc)
                dic.put(c, !dic.containsKey(c));
            for(char c : sc)
                if(dic.get(c)) return c;
            return ' ';
        }
    }

    class lufei2 {

        /**
         * 这个使用 linked-hashmap，判断时不用完整遍历字符串了，只需要遍历 hashmap
         * 可能会快一些
         * */
        public char firstUniqChar(String s) {
            Map<Character, Boolean> dic = new LinkedHashMap<>();
            char[] sc = s.toCharArray();
            for(char c : sc)
                dic.put(c, !dic.containsKey(c));
            for(Map.Entry<Character, Boolean> d : dic.entrySet()){
                if(d.getValue()) return d.getKey();
            }
            return ' ';
        }

    }

}

